package com.mengfou.sortextends;

import java.util.PriorityQueue;

/**
 * @author mengfou
 * 堆排序拓展
 */
public class HeapSortExtend {

    public static void main(String[] args) {
        int[] arr = new int[]{8, 2, 5, 6, 10, 19, 21, 16, 15};

        new HeapSortExtend().sortByHeap(arr, 3);
        for (int i : arr) {
            System.out.print(i+"\t");
        }
    }

    private void sortByHeap(int[] arr, int K){
        // 定义小根堆
//        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        MinHeap heap = new MinHeap();
        int heapSize = K + 1;
        int i = 0;
        for (; i < heapSize; i++) {
            heap.add(arr[i]);
        }
        int j = 0;
        for (; i < arr.length; j++) {
            heap.add(arr[i++]);
            arr[j] = heap.poll();
        }

        while(!heap.isEmpty()){
            arr[j++] = heap.poll();
        }
    }

    static class MinHeap{
        private int[] arr;
        private int index = 0;
        public MinHeap(){
            this(512);
        }
        public MinHeap(int cap){
            arr = new int[cap];
        }

        public void add(int val){
            arr[index++] = val;
            for (int i = 0; i < index; i++) {
                heapInsert(i);
            }
        }

        public boolean isEmpty(){
            return index == 0;
        }

        public int poll(){
            int val = arr[0];
            int size = --index;
            swap(arr, 0, size); // 和最后一个交换
            // 保证继续是小根堆
            heapify(size);
            return val;
        }

        private void heapify(int size) {
            int i = 0, left = 1;
            while(left < size){
                int minest = left + 1 < size && arr[left] > arr[left + 1] ? left + 1: left;
                minest = arr[i] < arr[minest] ? i : minest;
                if(minest == i) break;
                swap(arr, i, minest);
                i = minest;
                left = i * 2 + 1;
            }
        }


        private void heapInsert(int i) {
            while(arr[i] < arr[(i - 1) / 2]){
                swap(arr, i, (i - 1) / 2);
                i = (i - 1) / 2;
            }
        }

        private void swap(int[] arr, int left, int right) {
            int temp = arr[left] ^ arr[right];
            arr[left] = arr[left] ^ temp;
            arr[right] = arr[left] ^ temp;
        }
    }


}
